并查集算法


5.11 Union-Find算法详解

5.11.1 问题介绍

并查集算法主要是用来解决图论中“动态连通性”问题的。

简单来说动态连通性其实可以抽象成一幅图连线,比如说有一幅图,总共有10个节点,它们互不连通,分别用0-9进行标记

Union-Find算法需要实现以下这两个API

这里说的连通是一种等价关系,也就是说具有如下三个性质:

  • 自反性:p和p是连通的
  • 对称性:如果p和q是连通的,那么q和p也是连通的
  • 传递性:如果p和q是连通的,q和r是连通的,那么p和r也是连通的

那么在Union-Find算法中,调用union(0,1),那么0和1就会被连通,连通分量由10个降为9个,再调用union(1,2),连通分量降为8个,对应的:connected(0,2)会返回true,如图所示

5.11.2 基本思路

实现一个并查集的基本思路是:用森林(若干棵树)来表示图的动态连通性,用数组来具体这个森林,其中,森林是我们对于UnionFind的感性认知以及建模,而数组是我们实现这个模型的具体数据结构

怎么用森林来表示连通性呢?我们设定树的每个节点有一个指针指向其父节点,如果是根节点的话,这个指针就指向自己。

  • 定义数据结构
//记录连通分量
private int count;
//数组定义:节点x的父亲节点是parent[x]
private int[] parent;

public UnionFind(int n){
    //一开始各自不连通,那么就各自指向自己
    this.count = n;
    parent = new int[n];
    for(int i = 0;i<n;i++){
        parent[i] = i;
    }
}
  • 如果两个节点被连通,则让其中的(任意)一个节点的根节点接到另一个节点的根节点上

//将p节点和q节点进行链接
public void union(int p,int q){
    int rootP = find(p);
    int rootQ = find(q);
    if(rootP == rootQ){
        return ;
    }
    //将两棵树合并为一棵
    parent[rootP] = rootQ;
    //只要合并为一个连通图就可以了,这个顺序无所谓
    this.count -- ;
}
//判断p和q是否连同
public boolean isConnected(int p,int q){
    return false;
}
//返回图中有几个连通分量
public int count(){
    return count;
}

private int find(int x){//寻找根节点
    //根节点的parent[x] == x
    //这段代码的逻辑:x=parent[x],x赋值为其父节点的值
    //也就是向根节点逼近
    while (x != parent[x]) {
        x = parent[x];
    }
    return x;
}
  • 如果节点p和节点q连通的话,它们一定拥有相同的根节点
//判断p和q是否连同
public boolean isConnected(int p,int q){
    int rootP = find(p);
    int rootQ = find(q);
    return rootP == rootQ;
}
  • 分析时间复杂度,容易知道UnionFind所形成的树可能不是普通的二叉树,对于一般的树可能出现极端不平衡的情况,使得”树”几乎退化成”链表”,树的高度在最坏情况下可能变成N

5.11.3 平衡性优化

问题的关键在于,如何想办法避免树的不平衡呢?

我们想要知道哪种情况下出现不平衡的情况,其实形成树的过程是关键,因为形成树的过程中,决定了树的结构,来进行代码分析

//将p节点和q节点进行链接
public void union(int p,int q){
    int rootP = find(p);
    int rootQ = find(q);
    if(rootP == rootQ){
        return ;
    }
    //将两棵树合并为一棵
    parent[rootP] = rootQ;
    //只要合并为一个连通图就可以了,这个顺序无所谓
    this.count -- ;
}
  • 这段代码就是简单粗暴地把p所在的树接到q所在的树的节点下面,那么这里就可能出现头重脚轻的不平衡情况,有可能出现两种情况,如下图所示

我们是希望,小一些的树接到一些树的下面,这样就可以避免头重脚轻,更平衡一些,解决方法是一个备忘录的思想,设立一个size数组,记录每棵树所包含的节点数,我们不妨称为重量

//将p节点和q节点进行链接
public void union(int p,int q){
    int rootP = find(p);
    int rootQ = find(q);
    if(rootP == rootQ){
        return ;
    }
    //小树接到大树下面,比较平衡
    if(size[rootP] > size[rootQ]){
        parent[rootQ] = rootP;
        size[rootP] += size[rootQ];
    }else{
        parent[rootP] += rootQ;
        size[rootQ] += rootP;
    }
    this.count -- ;
}
  • 通过比较树的重量,就可以保证树的生长是相对平衡的,树的高度大致在logN 这个数量级,极大提升执行效率

findunionconnected的时间复杂度都下降为O(logN),即便数据规模上亿,所需时间也非常少

5.11.4 路径压缩

能否压缩每棵树的高度,使得树的高度始终保持为常数?

如果形成了这样的结构,这样find就能以O(1)的时间找到某一节点的根节点,相应的connectedunion复杂度都下降为O(1)

while (x != parent[x]) {
    parent[x] = parent[parent[x]];
    x = parent[x];
}
  • 要理解这段代码,首先一定要明确parent数组的定义,parent[i]是代表着i编号的节点的上一级节点

parent[x] = parent[parent[x]] ,来做阅读理解:parent[x]是什么?是x的父节点的编号(数字上解析),是x的父节点的指向关系(关系模型上解析),=是什么?是改变赋值,让x的父节点修改为什么?修改为x的父节点的父节点,也就是让x节点向上提升了一个层级

然后下一次,让x继续遍历这棵树,让x赋值为其父节点,这样的话就能够得到一棵相对平衡的树

//记录连通分量
private int count;
//数组定义:节点x的父亲节点是parent[x]
private int[] parent;
//新增一个数组记录树的重量
private int[] size;

public UnionFind(int n){
    //一开始各自不连通,那么就各自指向自己
    this.count = n;
    parent = new int[n];
    for(int i = 0;i<n;i++){
        parent[i] = i;
        size[i] = 1;//树的尺寸一开始都是1
    }
}

//将p节点和q节点进行链接
public void union(int p,int q){
    int rootP = find(p);
    int rootQ = find(q);
    if(rootP == rootQ){
        return ;
    }
    //小树接到大树下面,比较平衡
    if(size[rootP] > size[rootQ]){
        parent[rootQ] = rootP;
        size[rootP] += size[rootQ];
    }else{
        parent[rootP] = rootQ;
        size[rootQ] += rootP;
    }
    this.count -- ;
}
//判断p和q是否连同
public boolean isConnected(int p,int q){
    int rootP = find(p);
    int rootQ = find(q);
    return rootP == rootQ;
}
//返回图中有几个连通分量
public int count(){
    return count;
}

private int find(int x){//寻找根节点
    //根节点的parent[x] == x
    //这段代码的逻辑:x=parent[x],x赋值为其父节点的值
    //也就是向根节点逼近
    while (x != parent[x]) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

5.12 Union-Find算法的应用

Union-Find算法解决的是图的动态连通性问题,其关键是能否把原始问题抽象成一个有关图论的问题

算法的关键点如下:

  • parent数组记录每个节点的父节点,相当于指向父节点的指针,所以parent数组内实际存储着一个森林
  • size数组记录每棵树的重量,目的是调用union后树依然拥有平衡性,而不会退化成链表,影响操作效率
  • 在find函数中进行路径压缩,保证任意树的高度保持在常数,使得union和connectedAPI的时间复杂度为O(1)

5.12.1 DFS的替代方案

输入一个MXN的二维矩阵,其中包含字符X和O,让你找到矩阵中四面被X围住的O,并把它们替换为X

必须是四面被围的O才能被换成X,也就是说边界上的O一定不会被围,进一步,与边角上的O相连的O页不会被X围四面,也不会被替换

这道题的传统方法就是DFS算法,就是直接暴力搜索,其时间复杂度是O(MN),其中M和N分别为board的长和宽

我们可以用并查集的办法来解决这个问题,我们知道靠边的O不可能被替换,,然后与靠边的O相连的O也不可能被替换,我们可以抽象簇一个dummy节点,然后把这些O抽象成dummy节点的子节点

那么把这些关系抽象成一幅图,运用并查集算法,所有与dummy节点连通的节点是不会被替换的,反之,则是那些需要被替换的

首先要解决的问题是,根据我们的实现,UnionFind底层使用的是一维数组,构造函数需要传入这个数组的大小,而题目给的是一个二维棋盘

我们可以假设m是棋盘的行数,n是棋盘的列数,那么二维坐标就可以转化成(x*n+y),这是将二维坐标映射到一维的常用技巧

之前所描述的dummy节点是虚构的,需要给它留一个位置,索引[0...m*n-1]都是棋盘上元素的对应映射,那就让这个虚拟的dummy的节点占据索引m*n即可

public void solve(char[][] board) {
    if(board.length == 0){
        return;
    }
    int m = board.length;//行数
    int n = board[0].length;//列数
    UnionFind UF = new UnionFind(m*n+1);
    int dummy = m*n;
    //将首列的O与末列的O连通
    for(int i = 0;i<m;i++){
        if(board[i][0] == 'O'){
            UF.union(i*n,dummy);
        }
        if(board[i][n-1] == 'O'){
            UF.union(i*n+n-1,dummy);
        }
    }
    //将首行和末行的O连通
    for(int j = 0;j<n;j++){
        if(board[0][j] == 'O'){
            UF.union(j,dummy);
        }
        if(board[m-1][j] == 'O'){
            UF.union((m-1)*n+j,dummy);
        }
    }
    int[][] steps = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
    for (int i = 1;i<m-1;i++){
        for(int j =1;j<n-1;j++){
            if(board[i][j] == 'O'){
                //将此O与上下左右的O给连通
                for(int k =0;k<4;k++){
                    int x = i + steps[k][0];
                    int y = i + steps[k][1];
                    if (board[x][y] == 'O'){
                        UF.union(x*n+y,i*n+j);
                    }
                }
            }
        }
    }
    for(int i = 1;i<m-1;i++){
        for(int j = 1;j<n-1;j++){
            if(!UF.isConnected(dummy,i*n+j)){
                board[i][j] = 'X';
            }
        }
    }
}
class UnionFind {
    //记录连通分量
    private int count;
    //数组定义:节点x的父亲节点是parent[x]
    private int[] parent;
    //新增一个数组记录树的重量
    private int[] size;

    public UnionFind(int n){
        //一开始各自不连通,那么就各自指向自己
        this.count = n;
        parent = new int[n];
        for(int i = 0;i<n;i++){
            parent[i] = i;
            size[i] = 1;//树的尺寸一开始都是1
        }
    }

    //将p节点和q节点进行链接
    public void union(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ){
            return ;
        }
        //小树接到大树下面,比较平衡
        if(size[rootP] > size[rootQ]){
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }else{
            parent[rootP] += rootQ;
            size[rootQ] += rootP;
        }
        this.count -- ;
    }
    //判断p和q是否连同
    public boolean isConnected(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
    //返回图中有几个连通分量
    public int count(){
        return count;
    }

    private int find(int x){//寻找根节点
        //根节点的parent[x] == x
        //这段代码的逻辑:x=parent[x],x赋值为其父节点的值
        //也就是向根节点逼近
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}

5.12.2 判断算法等式

给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一:”a==b” 或 “a!=b”。在这里,a 和 b 是小写字母(不一定不同),表示单字母变量名。

只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true,否则返回 false。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/satisfiability-of-equality-equations
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 每个算式equations装着若干字符串表示的算式,每个算式equations[i]都是4,而且只有这两种情况等于或者不等于
  • 如果equations中所有的算式都不会冲突,那么返回true,否则返回false
  • 动态连通性其实就是一种等价关系,具有自反性、传递性、对称性,其实==也是一种等价关系,具有这些性质,所以这个问题用UF算法就很自然
  • 核心思路:将equations中的算式根据==和!=分成两部分,先处理==等式,使得他们通过相等关系互通,然后处理!=算式,检查不等关系是否破坏关系的连通性
public boolean equationsPossible(String[] equations) {
    //建立26个字母连通关系
    UnionFind unionFind  = new UnionFind(26);
    for (String equation : equations) {
        if(equation.charAt(1) == '='){
            char x = equation.charAt(0);
            char y = equation.charAt(3);
            unionFind.union(x-'a',y-'a');
        }
    }
    //检查不等关系
    for (String equation : equations) {
        if(equation.charAt(1) == '!'){
            char x = equation.charAt(0);
            char y = equation.charAt(3);
            if(unionFind.isConnected(x-'a',y-'a')){
                return false;
            }
        }
    }
    return true;
}

文章作者: 穿山甲
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 穿山甲 !
  目录